The invention relates generally to elevator group control, and more particularly to optimizing group elevator scheduling. BACKGROUND OF THE INVENTION
Group elevator scheduling is a well-known problem in industrial control and operations research with significant practical implications, Bao et al., xe2x80x9cElevator dispatchers for down-peak traffic,xe2x80x9d Technical Report, University of Massachusetts, Department of Electrical and Computer Engineering, Amherst, Mass., 1994. Given a hall call generated at one of the floors of a building with multiple elevator shafts, the objective of elevator group control is to decide which car to use to serve the hall call.
In some elevator systems, the controller assigns a car to the hall call as soon as the call is signaled, and immediately directs the passenger who signaled the hall call to the corresponding shaft by sounding a chime. While in other systems, the chime is sounded when the assigned car arrives at the floor of the hall call.
That difference influences car assignment in two ways. Making an early assignment to service the hall call impairs the performance of the controller when the assignment is incorrect. That makes the assignment problem harder because the controller has to consider events over a longer time interval. Also, after a decision is made, the decision cannot be changed.
Scheduling policy is subject to constraints arising from passenger expectations, destinations, and elevator movement. The constraints can include passengers arrival rates on all floors, fixed or variable inter-floor travel times, and fixed passenger destinations and/or origins, etc.
While one objective of elevator control is to minimize the cost of operating the system, e.g., the cost measured in terms of waiting and/or travel times of passengers in all types of traffic, several traffic patterns are of special interest because those patterns pose extraordinary demand on the elevator group and its controller. Such traffic patterns are up-peak traffic, which arises at the beginning of the workday in an office building, down-peak traffic, which arises at the end of the workday, and lunch traffic, down first, and up a little later.
Up-peak traffic is characterized by a large number of passengers arriving in the lobby, boarding cars and exiting the cars at the upper floors while, simultaneously, a lesser number of passengers travel between floors other than the lobby. Such a traffic pattern has uncertainty in the destination floors of passengers, while the floor of the car call is most frequently the lobby.
The reverse situation is down-peak traffic, when most passengers board cars at one of the upper floors and exit the car at the lobby, while a lesser number of passengers travel to destinations other than the lobby. Correspondingly, the amount of uncertainty in the case of down-peak traffic is opposite to that of up-peak traffic because there is little uncertainty about the destination floor, i.e., the lobby, but there is greater uncertainty in the call floor.
Lunch traffic combines elements of down-peak and up-peak traffic. The system starts with down-peak traffic and then slowly shifts to up-peak traffic. In addition to having uncertainty in both call and destination floors, the properties of passenger flow shift with time.
Elevator scheduling could be expressed as combinatorial optimization problems. Solutions to these problems are characterized by identifying an optimum solution for transitioning from a current state to a desired state, where the desired state is selected from all possible future states. In principle, combinatorial optimization problems could be solved by evaluating all possible combinations of choices and selecting only that combination that gives the most favorable result.
However, other than for simple problems, the number of possible choices increases exponentially and rapidly becomes so large that, even when digital computers are employed, the solution of a single problem on a single processor may take hours, days, sometimes even months or years, see below. Up to now, prior art elevator scheduling systems and methods have not considered evaluating all possible solutions to find a best solution. Typically, only a subset of solutions are considered, or the operation of the elevators is severely in constrained in some way to make the problem solvable in real-time.
For example, partial solutions have been obtained for the limited case of purely up-peak traffic, and the constraints that all passengers arrive in the lobby at a fixed rate and no other call floors are allowed, see, e.g., Pepyne et al., xe2x80x9cOptimal dispatching control for elevator systems during up peak traffic,xe2x80x9d IEEE transactions on control systems technology, 5(6):629-643, 1997. In order to make the problem manageable, the service time of elevators is assumed to come from a fixed exponential distribution.
Many prior art controllers used the principle of collective control, see Strakosch et al., xe2x80x9cVertical transportation: elevators and escalators,xe2x80x9d John Wiley and Sons, Inc., New York, N.Y., 1983. With collective control, cars are constrained to always stop at the nearest call in their running direction. That strategy ignores the total state of the system and usually results in bunching. Bunching is a phenomenon where several cars arrive at the same floor at about the same time, with all cars but one wasting time, see Hikihara et al., xe2x80x9cEmergent synchronization in multi-elevator system and dispatching control,xe2x80x9d IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E80-A(9):1548-1553, 1997. They concluded that the bunching effect occurring in down-peak traffic was due to synchronization between multiple cars.
Another prior art approach constrains operation by zoning, or sectoring. There, the building is divided into zones and each car is assigned a single zone. While that approach avoids bunching, it also ignores the total state of the system.
Other control techniques and heuristics can also be used. Mitsubishi Electric""s elevator group control system, xe2x80x9cAI-2100N,xe2x80x9d is based on an expert system with fuzzy rules. That system relies on expert judgment of humans to prescribe a good assignment of calls. That system cannot determine a solution to a scheduling problem by itself. Rather, that system identifies the problem and employs preprogrammed human derived solutions to the problem, see Ujihara et al., xe2x80x9cThe revolutionary AI-2000 elevator group-control system and the new intelligent option series,xe2x80x9d Mitsubishi Electric Advance, 45:5-8, 1988, and Ujihara et al., xe2x80x9cThe latest elevator group-control system,xe2x80x9d Mitsubishi Electric Advance, 67:10-12, 1994.
The Otis elevator Relative System Response (RSR) method and its variants estimate, for each car, the time it would take to service the already assigned calls when a new call arises, and assigns the car with the lowest remaining service time to that call. The RSR methods are examples of greedy methods They either are constrained to have a predetermined assignment of calls, or never reconsider an assignment.
A more sophisticated group of methods use non-greedy strategies which recompute car assignments after each change of state. As noted, such methods are not applicable to certain elevator groups where reassignments are not allowed. Examples of such methods are Finite Intervisit Minimization (FIM) and Empty the System Algorithm (ESA), see Bao et al. While they have been demonstrated to outperform simpler methods by a margin of 34%, FIM and ESA are limited to down-peak traffic because they presume that the destination of all passengers is constrained to be the lobby. That method is not optimal in real world elevator systems where the lobby is certainly not the only desired destination.
Furthermore, such methods are constrained to assume no new passenger arrivals occur while a call is processed, and find the best strategy to service the existing calls given that simplification. Thus, by failing to take into account the stochastic component of the elevator system, a significant number of potential future states of the system are totally ignored. A method that could take into account the stochastic component of elevator group behavior has a potential to outperform those methods.
One such method uses neural networks and Q-leaming to provide an asynchronous method for stochastic optimal control, see Crites et al., xe2x80x9cImproving elevator performance using reinforcement learning,xe2x80x9d Touretzky et al. Ed., MIT Press, xe2x80x9cAdvances in Neural Information Processing Systems, volume 8, pages 1017-1023, 1996. Although their method performed slightly better than FIM and ESA for one specific down-peak profile, it took 60000 hours (over seven years) of simulated elevator operation to converge. Obviously, this is not practical for real-time elevator control. One possible reason for its slow convergence is the generally inefficient use of training samples by Q-learning. Q-learning discards training samples as soon as it makes a small adjustment in the parameters controlling the current scheduling policy.
Therefore, what is needed is a method for elevator control which determines every possible choice and selects a car to answer a hall call that minimizes passenger waiting time in all types of passenger flow situations.
The invention provides a method for controlling an elevator system including multiple elevator cars and floors. A new waiting passenger at one of the floors places a hall call. The hall call is received and an expected cost for servicing each waiting passenger including the new waiting passenger is estimated. The elevator car that minimizes the total cost for servicing all of the waiting passengers is selected to respond to the hall call.
More particularly, in response to receiving the hall call, the method determines, for each car, all possible future states of the elevator system. The states are dependent on discrete and continuous variables. The continuous variables are discretized. Both the discrete and discretized variables are applied to a trellis structure corresponding to a number of all possible future states of the system. A path across the trellis structure is evaluated according to transitional probabilities of transitioning between states for each car in the system. The car with a minimum cost according to an estimated path across the trellis is selected to serve the hall call. The method is applicable to any type of traffic. It is particularly well-suited for up-peak traffic because it handles efficiently the uncertainty in passenger destinations.